#include <iostream>
#include <set>
#include <utility>
#include <vector>

using std::cout;
using std::endl;
using std::multiset;
using std::pair;
using std::vector;

template <typename Container>
void display(const Container &con)
{
    for(auto &elem : con)
    {
        cout << elem << "  ";
    }
    cout << endl;
}

void test()
{
    //multiset的特征：
    //1、存放的是key类型，key值不唯一，可以重复
    //2、默认情况下，会按照key值进行升序排列
    //3、multiset的底层使用的是红黑树结构
    //4、和set基本一样，除了insert单个值返回类型不是pair
    multiset<int> number={1, 3, 5, 8, 9, 7, 3, 6, 5, 2};
    //multiset<int, std::greater<int> > number{1, 3, 5, 8, 9, 7, 3, 6, 5, 2};
    //可以从大到小排
    display(number);

    cout << endl << "count查找" << endl;
    size_t cnt = number.count(3);
    cout << "cnt = " << cnt << endl;

    cout << endl << "find查找" << endl;
    multiset<int>::iterator it = number.find(4);
    if(it != number.end())
    {
        cout << "该元素在multiset中" << *it << endl;
    }
    else
    {
        cout << "该元素不在multiset中" << endl;
    }

    cout<<endl<<"bound，返回迭代器"<<endl;
    auto it2=number.lower_bound(5); //第一个大于等于
    cout<<*it2<<endl;
    auto it3=number.upper_bound(5); //第一个大于
    cout<<*it3<<endl;

    cout<<endl<<"range，返回第一个≥、>的迭代器"<<endl;
    pair<multiset<int>::iterator,multiset<int>::iterator>
        ret =number.equal_range(5);
    while(ret.first != ret.second){
        cout<<*ret.first<<endl;
        ++ret.first;
        //所以返回的两个指针和lower、upper相同
        //可以在此实现count函数
    }

    cout << endl << "insert插入，因为可以有重复元素，所以返回类型只有迭代器" << endl;
    auto it7=number.insert(10);
    cout<<*it7<<endl;
    display(number);

    cout << endl;
    //迭代器范围地插入
    vector<int> vec = {1, 3, 5, 9, 11, 34, 67, 4, 2};
    number.insert(vec.begin(), vec.end());
    display(number);

    cout << endl;
    //大括号插入
    number.insert({12, 88, 33});
    display(number);

    cout << endl << "删除操作，可以删除指定位置也可以全删" << endl;
    it = number.begin();
    ++it;
    ++it;
    cout << "*it = " << *it << endl;
    number.erase(it);
    display(number);
    number.erase(5);//5全被删了
    display(number);
    
    cout << endl << "multiset不支持下标访问" << endl;
    //cout << "number[1] = " << number[1] << endl;

    cout << endl << "不支持修改，因为multiset是红黑树，修改了容易乱" << endl;
    it = number.begin();
    ++it;
    ++it;
    cout << "*it = " << *it << endl;
    /* *it = 100;//error */
}

int main(int argc, char *argv[])
{
    test();
    return 0;
}


